<?php
/**
 * User: LRZ
 * Date: 2020/1/21
 * Time: 17:20
 */

/**
 *  1122.数组的相对排序
 *
 *  标签：排序、数组
 *
 *  给你两个数组，arr1 和 arr2：
 *      arr2 中的元素各不相同
 *      arr2 中的每个元素都出现在 arr1 中
 *  对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 *  示例：
 *      输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 *      输出：[2,2,2,1,4,3,3,9,6,7,19]
 *   
 *  提示：
 *      arr1.length, arr2.length <= 1000
 *      0 <= arr1[i], arr2[i] <= 1000
 *      arr2 中的元素 arr2[i] 各不相同
 *      arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/relative-sort-array
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);


$arr1 = [2, 3, 1, 3, 2, 4, 6, 19, 9, 2, 7];
$arr2 = [2, 1, 4, 3, 9, 6];
$res  = relativeSortArray($arr1, $arr2);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function relativeSortArray($arr1, $arr2)
{
    $res        = [];
    $nums       = [];
    $redundancy = [];
    $index      = 0;

    foreach ($arr1 as $k => $v) {
        if (!isset($nums[$v])) {
            $nums[$v] = 1;
        } else {
            $nums[$v]++;
        }
    }

    foreach ($arr2 as $k => $v) {
        while ($nums[$v] > 0) {
            $res[$index++] = $v;
            $nums[$v]--;
        }
    }

    foreach ($nums as $k => $v) {
        while ($v > 0) {
            $redundancy[] = $k;
            $v--;
        }
    }

    sort($redundancy);

    return array_merge($res,$redundancy);
}